This invention is in the field of communications, and is more specifically directed to the encoding of digital information in such communications.
High-speed data communication services, for example in providing high-speed Internet access, have become a widespread utility for many businesses, schools, and homes. In its current stage of development, this access is provided by an array of technologies. Recent advances in wireless communications technology have enabled localized wireless network connectivity according to the IEEE 802.11 standard to become popular for connecting computer workstations and portable computers to a local area network (LAN), and typically through the LAN to the Internet. Broadband wireless data communication technologies, for example those technologies referred to as “WiMAX” and “WiBro”, and those technologies according to the IEEE 802.16d/e standards, have also been developed to provide wireless DSL-like connectivity in the Metro Area Network (MAN) and Wide Area Network (WAN) context.
Multiple-input-multiple-output (MIMO) communication techniques have recently attracted attention, especially in the wireless LAN context. In a general sense, MIMO communications are realized by providing multiple signal paths (i.e., RF data path, or “chain”, and antenna) both at a transmitter and at a receiver. In this manner, the transmitted information is either redundantly or independently transmitted over multiple spatial streams between a transmitter antenna and a receiver antenna. The spatial diversity provided by the MIMO approach provides either improved data rate or improved bit error rate in the signal, after combining of the multiple spatial streams at the receiver. These improvements are attractive in any wireless communications context, including wireless LAN (or MAN or WAN) technology, and wireless telephony. An overview of MIMO technology is provided in Gesbert et al., “From Theory to Practice: An Overview of MIMO Space-Time Coded Wireless Systems”, Journal on Selected Areas in Communications, Vol. 21, No. 3 (IEEE, April 2003), pp. 281-302.
In the wireless LAN context, MIMO communication technology is being investigated for use in conjunction with orthogonal frequency-division multiplexing (OFDM) techniques. As known in the art, OFDM refers to a broadband communications approach in which modulated signals are transmitted over multiple narrow-bandwidth (e.g., 20 kHz) channels. Standardization efforts for use of MIMO OFDM wireless LAN communications have been ongoing in the industry, specifically with reference to the IEEE 802.11n standard. It is contemplated that wireless LAN communications under the eventual 802.11n standard will be able to reach 250 Mbit/second data rates, at distances of up to 50 meters.
A problem that is common to all data communications technologies, including of course MIMO OFDM communications, is the corruption of data by noise. As is fundamental in the art, the signal-to-noise ratio for a communications channel is a degree of goodness of the communications carried out over that channel, as it conveys the relative strength of the signal that carries the data (as attenuated over distance and time), to the noise present on that channel. These factors relate directly to the likelihood that a data bit or symbol as received differs from the data bit or symbol as transmitted. This likelihood of a data error is reflected by the error probability for the communications over the channel, commonly expressed as the Bit Error Rate (BER) ratio of errored bits to total bits transmitted. In short, the likelihood of error in data communications must be considered in developing a communications technology. Techniques for detecting and correcting errors in the communicated data must be incorporated for the communications technology to be useful.
Error detection and correction techniques are typically implemented by the technique of redundant coding. In general, redundant coding inserts data bits into the transmitted data stream that do not add any additional information, but that indicate, on decoding, whether an error is present in the received data stream. More complex codes provide the ability to deduce the true transmitted data from a received data stream even if errors are present.
Many types of redundant codes that provide error correction have been developed. One type of code simply repeats the transmission, for example by sending the payload followed by two repetitions of the payload, so that the receiver deduces the transmitted data by applying a decoder that determines the majority vote of the three transmissions for each bit. Of course, this simple redundant approach does not necessarily correct every error, but greatly reduces the payload data rate. In this example, a predictable likelihood exists that two of three bits are in error, resulting in an erroneous majority vote despite the useful data rate having been reduced to one-third. More efficient approaches, such as Hamming codes, have been developed toward the goal of reducing the error rate while maximizing the data rate.
The well-known Shannon limit provides a theoretical bound on the optimization of decoder error as a function of data rate. The Shannon limit provides a metric against which codes can be compared, both in the absolute and relative to one another. Since the time of the Shannon proof, modem data correction codes have been developed to more closely approach the theoretical limit. An important class of these conventional codes includes “turbo” codes, which encode the data stream by applying two convolutional encoders. One of these convolutional encoders encodes the datastream as given, while the other encodes a pseudo-randomly interleaved version of the data stream. The results from the two encoders are interwoven to produce the encoded data stream.
Another class of known redundant codes are the Low Density Parity Check (LDPC) codes. The fundamental paper describing these codes is Gallager, Low-Density Parity-Check Codes, (MIT Press, 1963), monograph available at http://www.inference.phy.cam.ac.uk/mackay/gallager/papers/. In these codes, a sparse matrix H defines the code, with the encodings c of the payload data satisfying:Hc=0  (1)over Galois field GF(2). Each encoding c consists of the source message ci combined with the corresponding parity check bits cp for that source message ci. The encodings c are transmitted, with the receiving network element receiving a signal vector r=c+n, n being the noise added by the channel. Because the decoder at the receiver also knows matrix H, it can compute a vector z=Hr. However, because r=c+n, and because Hc=0:z=Hr=Hc+Hn=Hn  (2)The decoding process thus involves finding the most sparse vector x that satisfies:Hx=z  (3)over GF(2). This vector x becomes the best guess for noise vector n, which can be subtracted from the received signal vector r to recover encodings c, from which the original source message ci is recoverable.
There are many known implementations of LDPC codes. Some of these LDPC codes have been described as providing code performance that approaches the Shannon limit, as described in MacKay et al., “Comparison of Constructions of Irregular Gallager Codes”, Trans. Comm., Vol. 47, No. 10 (IEEE, Oct. 1999), pp. 1449-54, and in Tanner et al., “A Class of Group-Structured LDPC Codes”, ISTCA-2001 Proc. (Ambleside, England, 2001).
In theory, the encoding of data words according to an LDPC code is straightforward. Given enough memory or small enough data words, one can store all possible code words in a lookup table, and look up the code word in the table according to the data word to be transmitted. But modem data words to be encoded are on the order of 1 kbits and larger, rendering lookup tables prohibitively large and cumbersome. Accordingly, algorithms have been developed that derive codewords, in real time, from the data words to be transmitted. A straightforward approach for generating a codeword is to consider the n-bit codeword vector c in its systematic form, having a data or information portion ci and an m-bit parity portion cp such that c=(c1|cp). Similarly, parity matrix H is placed into a systematic form Hsys, preferably in a lower triangular form for the m parity bits. In this conventional encoder, the information portion ci is filled with n-m information bits, and the m parity bits are derived by back-substitution with the systematic parity matrix Hsys. This approach is described in Richardson and Urbanke, “Efficient Encoding of Low-Density Parity-Check Codes”, IEEE Trans. on Information Theory, Vol. 47, No. 2 (Feb. 2001), pp. 638-656. This article indicates that, through matrix manipulation, the encoding of LDPC codewords can be accomplished in a number of operations that approaches a linear relationship with the size n of the codewords. However, the computational efficiency in this and other conventional LDPC encoding techniques does not necessarily translate into an efficient encoder hardware architecture. Specifically, these and other conventional encoder architectures are inefficient because they typically involve the storing of inverse matrices, by way of which the parity check of equation (1), or a corollary, is solved in the encoding operation.
By way of further background, copending patent application Ser. No. 10/329,597, filed Dec. 26, 2002, now published as U.S. Patent Application Publication No. U.S. 2004/0034828, and copending patent application Ser. No. 10/806,879, filed Mar. 23, 2004, and now published as U.S. Patent Application Publication No. U.S. 2004/0194007 A1, both commonly assigned herewith and incorporated herein by this reference, describe a family of structured irregular LDPC codes, and decoding architectures for those codes. The quasi-cyclic structure of this family of LDPC codes can also provide efficiencies in the hardware implementation of the encoder, as described in copending patent application Ser. No. 10/724,280, filed Nov. 28, 2003, now published as U.S. Patent Application Publication No. U.S. 2004/0148560 A1, commonly assigned herewith and incorporated herein by this reference. The encoder and encoding method that are described in U.S. Patent Application Publication No. U.S. 2004/0148560 A1 follow a generalized approach, and are capable of handling such complications as row rank deficiency.
By way of still further background, copending patent application Ser. No. 11/201,391, filed Aug. 10, 2005 and published as U.S. Patent Application Publication No. U.S. 2006/0036926, commonly assigned herewith and incorporated herein by this reference, describes constraints on this family of structured irregular LDPC codes that enable recursive, and efficient, encoding of communications.
By way of still further background, copending patent application Ser. No. 11/284,929, filed Nov. 22, 2005 and published as U.S. Patent Application Publication No. U.S. 2006/0123277 A1, commonly assigned herewith and incorporated herein by this reference, describes the shortening and puncturing of systematic codewords, and more specifically describes the selection of the number of shortened bits and the number of punctured bits from a given codeword length and code rate, for encoding according to a different selected codeword length. The approach described in this U.S. Patent Application Publication No. U.S. 2006/0123277 A1 is believed to be particularly useful in connection with broadband wireless MAN communications according to the IEEE 802.16 standard.
By way of still further background, it is known to restructure a codeword arrangement in response to a comparison of the fraction of information bits that are to be shortened to the fraction of parity bits that are to be punctured.
As fundamental in the art of coded communications, the codeword length greatly affects the efficiency and performance of the communications system. As such, it is desirable to optimize communications by wisely selecting these code parameters. However, in the context of MIMO OFDM communications, many factors in the particular system implementation and operation are present that ought to be taken into account in selecting the optimum codeword length. These factors include the number of transmit antennae (and RF chains), the number of receive antennae (and RF chains), the number of OFDM subchannels, packet lengths, whether space-time block coding (“STBC”) will be used to transmit a single spatial stream across multiple antennae, the modulation scheme applied to individual OFDM subchannels (e.g., 16-QAM, 64-QAM), the desired code rate, whether a short guard interval option is used, and the like.
Convolutional error correcting codes can be readily and flexibly adapted to a wide range of codeword lengths and code rates. It is desirable to obtain the important benefits provided by LDPC codes; however, LDPC codes operate on fixed block sizes, and as such are not easily adapted to varying selections of codeword length and code rate. As discussed above, and as described in the above-incorporated U.S. Patent Application Publication No. U.S. 2006/0123277 A1, it is also desirable to have a minimum number of codeword lengths and code rates in modern LDPC transceivers, so that the memory and computational requirements can be kept modest.